package src.week16;

public class Prim {

    public static void PRIM(int [][] graph,int start,int n){
        int [][] mins=new int [n][2];
        for(int i=0;i<n;i++){
            if(i==start){
                mins[i][0]=-1;
                mins[i][1]=0;
            }else if( graph[start][i]!=-1){//说明存在（start，i）的边
                mins[i][0]=start;
                mins[i][1]= graph[start][i];
            }else{
                mins[i][0]=-1;
                mins[i][1]=Integer.MAX_VALUE;
            }
        }
        for(int i=0;i<n-1;i++){
            int minV=-1,minW=Integer.MAX_VALUE;
            for(int j=0;j<n;j++){
                if(mins[j][1]!=0&&minW>mins[j][1]){
                    minW=mins[j][1];
                    minV=j;
                }
            }
            mins[minV][1]=0;
            System.out.println("最小生成树的第"+i+"条最小边是（"+(mins[minV][0]+1)+","+(minV+1)+"），权重="+minW);
            for(int j=0;j<n;j++){
                if(mins[j][1]!=0){
                    if( graph[minV][j]!=-1&& graph[minV][j]<mins[j][1]){
                        mins[j][0]=minV;
                        mins[j][1]= graph[minV][j];
                    }
                }
            }
        }
    }
    public static void main(String [] args){
        int [][] tree={
                {1,2,3,4,5,6},
                {2,3,4,5,6,7},
                {3,4,5,6,7,8},
                {4,5,6,7,8,9},
                {5,6,7,8,9,10},
                {6,7,8,9,10,11}
        };
        Prim.PRIM(tree, 0, 6);
    }
}